
#ifndef _POLYNOMIAL_H
#define _POLYNOMIAL_H

#include<iostream>
#include<vector>
#include<string>
#include<map>

//Traits for polynomial reading
template<typename T>
class polynomial_traits{
      public:
             static std::istream& read(
                    std::istream& is,
                    T& p);  //This gets a polynomial type when called
};

template<typename T>
class polynomial{
      public:
             polynomial(){}  //Represents a null polynomial
             polynomial(std::vector<std::string> vrs);
             polynomial(std::vector<std::string> vrs, T coeff);
             polynomial(std::vector<std::string> vrs, std::vector<int> degree, T coeff);
             polynomial(T coeff){
                 std::vector<int> deg;
                 ht[deg]=coeff;
             }
             //polynomial(degreeStructureType ht, varsType vrs);  //unsafe function
             polynomial(const polynomial& right);
             
             polynomial add(polynomial right);
             polynomial multiply(polynomial right);
             polynomial power(int n);
             //Substitution in polynomial
             polynomial substitute_var(std::string var_to_subs, polynomial new_var);
             polynomial substitute_var(std::string var_to_subs, std::string new_var);
             polynomial expand();
             int degree();
             int degree_var(std::string vr);
             
             //Operator overloading
             polynomial operator+(polynomial& right);
             polynomial operator-(polynomial& right);
             polynomial operator*(polynomial& right);
             polynomial& operator=(polynomial& right);
             //polynomial operator=(polynomial right);
             
             bool operator==(polynomial& right);
             bool operator!=(polynomial& right);
             
             //Friend operators for streams
             template<typename R>
             friend std::istream& operator>>(std::istream& is, polynomial<R>& p);
             
             template<typename R>
             friend std::ostream& operator<<(std::ostream& os, polynomial<R> p);
             
             //To handle exceptions
             class polynomial_exception: public std::exception{
                 virtual const char* what() const throw(){
                     return "Error in polynomial.";
                 }
             };
             
             //Print the values of the variables in this polynomial for debug purposes
             void print_info(){
                 std::cout<<"ht=[";
                 typename std::map<std::vector<int>,T>::iterator it = ht.begin();
                 if(it!=ht.end()){
                     std::cout<<"[";
                     std::vector<int> vec_temp = it->first;
                     typename std::vector<int>::iterator it_deg = vec_temp.begin();
                     if(it_deg!=vec_temp.end()){
                         std::cout<<*it_deg;
                         ++it_deg;
                     }
                     for(;it_deg!=vec_temp.end();++it_deg){
                         std::cout<<","<<*it_deg;
                     }
                     std::cout<<"]=>"<<(it->second);
                     ++it;
                 }
                 for(;it!=ht.end();++it){
                     std::cout<<",";
                     std::cout<<"[";
                     std::vector<int> temp_vector = it->first;
                     typename std::vector<int>::iterator it_deg = temp_vector.begin();
                     if(it_deg!=temp_vector.end()){
                         std::cout<<*it_deg;
                         ++it_deg;
                     }
                     for(;it_deg!=temp_vector.end();++it_deg){
                         std::cout<<","<<*it_deg;
                     }
                     std::cout<<"]=>"<<(it->second);
                 }
                 std::cout<<"], vars=[";
                 typename std::vector<term>::iterator it_vec = vars.begin();
                 if(it_vec!=vars.end()){
                     (*it_vec).write(std::cout);
                     ++it_vec;
                 }
                 for(;it_vec!=vars.end();++it_vec){
                     std::cout<<",";
                     (*it_vec).write(std::cout);
                 }
                 std::cout<<"]";
             }
      private:
              //Definition of term class
              class term{
                    public:
                           term(void* v, std::string t):term_value(v),term_type(t){}
                           term(const term& right):term_type(right.term_type){
                               if(right.term_type=="string")
                                   term_value = new std::string(*(std::string*)right.term_value);
                               else if(right.term_type=="polynomial")
                                   term_value = new polynomial(*(polynomial*)right.term_value);
                               else ;  //Should throw an exception about term type
                           }
                           ~term(){
                               if(term_value){
                                   if(term_type=="string"){
                                       delete (std::string*)term_value;
                                   }
                                   else if(term_type=="polynomial"){
                                       delete (polynomial*)term_value;
                                   }
                               }
                           }
                           void* get_term_pointer(){return term_value;}
                           std::string get_term_type(){return term_type;}
                           //Some operator overload (some are important)
                           bool operator==(term& right){
                                //Add term comparision code here
                                if(term_type!=right.term_type) return false;
                                if(term_type=="string"){
                                    std::string* st_pointer = (std::string*)term_value;
                                    std::string* st_pointer_right = (std::string*)right.term_value;
                                    //return (st_pointer->compare(*st_pointer_right)==0);
                                    return *st_pointer==*st_pointer_right;
                                }
                                else if(term_type=="polynomial"){
                                     polynomial* pl_pointer = (polynomial*)term_value;
                                     polynomial* pl_pointer_right = (polynomial*)right.term_value;
                                     //return (pl_pointer->compare(*pl_pointer_right));
                                     return *pl_pointer==*pl_pointer_right;
                                }
                                return false;
                           }
                           
                           term& operator=(term& right){
                               if(term_value!=0){
                                   if(term_type=="string"){
                                       delete (std::string*)term_value;
                                   }
                                   else if(term_type=="polynomial"){
                                       delete (polynomial*)term_value;
                                   }
                               }
                               term_type=right.term_type;
                               if(term_type=="string"){
                                   std::string *str_pointer = (std::string*)right.term_value;
                                   term_value=new std::string(*str_pointer);
                               }
                               else if(term_type=="polynomial"){
                                   polynomial *pol_pointer = (polynomial*)right.term_value;
                                   term_value = new polynomial(*pol_pointer);
                               }
                               return right;
                           }
                           
                           std::ostream& write(std::ostream& os){
                               if(term_type=="string"){
                                   std::string *str_pointer = (std::string*)term_value;
                                   os<<*str_pointer;
                               }
                               else if(term_type=="polynomial"){
                                   polynomial *pol_pointer = (polynomial*)term_value;
                                   os<<"("<<*pol_pointer<<")";
                               }
                               return os;
                           }
                           std::istream& read(std::istream& is){
                               return is;
                           }
                           
                    private:
                            void* term_value;
                            std::string term_type;
              };
              //Private varibles declaration
              std::map<std::vector<int>,T> ht;
              std::vector<term> vars;  //The polynomial is represented as a tree
              
              //Private functions declaration
              polynomial multiply_term(std::vector<term> vrs1, std::vector<int> deg1, T coeff1, 
                                       std::vector<term> vrs2, std::vector<int> deg2, T coeff2);
              polynomial expand_term(std::vector<term> vrs, std::vector<int> deg, T coeff);
              std::vector<std::string> get_all_string_vars();
              std::vector<std::string> merge_vars(std::vector<std::string> vrs1, std::vector<std::string> vrs2);
              bool compare_term(std::vector<term> vrs1, std::vector<int> deg1, std::vector<term> vrs2, std::vector<int> deg2);
              bool compare_degrees(std::vector<int> deg1, std::vector<int> deg2);
              bool search_degree(typename std::map<std::vector<int>,T>::iterator map_iterator_begin,
                                 typename std::map<std::vector<int>,T>::iterator map_iterator_end,
                                 std::vector<int> deg);
              //Private function assing_variable correspond to term constructor
              //Stream auxiliary functions
              std::istream& read(std::istream& is);  //Equivalence to toString
              std::ostream& write(std::ostream& os);
};  //polynomial

#endif
